//287.寻找重复数
//https://leetcode.cn/problems/find-the-duplicate-number
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        //快慢指针 将数字看作下标 此时形成链表
        //链表中的环是通过快慢指针 先让两指针在环中相遇
        //然后让一个指针从链表起始位置开始走 另一个从相遇点开始走 最后相遇点就是环入口
        // 1->2->3->4->2 之所以会有相遇点就是形成环

        int first = 0,tail = 0;
        do
        {
            tail = nums[tail];
            first = nums[nums[first]];
        }while(first != tail);
        //此时first是环中相遇点
        tail = 0;
        while(first != tail)
        {
            tail = nums[tail];
            first = nums[first];
        }
        return tail;
    }
};